package cn.genmer.test.security.leetcode.medium;

/**
 * @program: Algorithm_to_practice
 * @description: 189. 轮转数组 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
 * @author: Genmer
 * @create: 2020-10-15 01:26
 **/
public class ArrayElementMobile {
    public static void main(String[] args) {
        int[] nums = {1,2,2,5,6,8};

        System.out.println("转之前：");
        for (int i=0; i<nums.length;i++){
            System.out.print(nums[i]+" ");
        }
        rotate(nums,3);
        System.out.println();
        System.out.println("转之后：");
        for (int i=0; i<nums.length;i++){
            System.out.print(nums[i]+" ");
        }
    }

    /**
     * 数组元素旋转
     * @param nums
     * @param k
     */
    public static void rotate(int[] nums, int k){
        int temp;
        int maxIndex=nums.length-1;
        for (int i=0;i<k;i++){
            // 一次位移一个元素
            temp = nums[maxIndex];

            for (int j=maxIndex; j>0;j--){
                nums[j] = nums[j-1];
            }
            nums[0] = temp;
        }
    }

    /**
     * 官方题解 - 最后一种解法，通过计算有多少个数会从尾 - 头，翻转数组实现
     * @param nums
     * @param k
     */
    public void rotate2(int[] nums, int k) {
        int length = nums.length;
        // int[] newArray = new int[length];
        // for(int i=0; i<length; ++i){
        //     newArray[(i+k) % length] = nums[i];
        // }
        // System.arraycopy(newArray, 0, nums, 0, length);

        // 第一步，整个数组翻转
        reverse(nums, 0, length-1);
        // 第二步，翻转会从尾部转到头部的k的元素
        reverse(nums,0, k % length - 1);
        // 第三步，翻转k%length后面的数
        reverse(nums, k%length, length-1);
    }

    private static void reverse(int[] nums, int start, int end){
        while(start < end){
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start += 1;
            end -= 1;
        }
    }

    /**
     * 官方题解，俩个数组，通过计算位置实现把挪移后的值放入新数组，最后复制回来
     * @param nums
     * @param k
     */
    public void rotate3(int[] nums, int k) {
        int temp;
        for (int i=0;i<k;i++){
            temp = nums[nums.length-1];

            for (int j=nums.length-1; j>0;j--){
                nums[j] = nums[j-1];
            }
            nums[0] = temp;
        }
    }
}
